// https://leetcode.cn/problems/assign-cookies/description/

// 算法思路总结：
// 1. 使用贪心策略分配饼干满足孩子
// 2. 将孩子胃口和饼干尺寸分别排序
// 3. 用最小尺寸饼干优先满足最小胃口孩子
// 4. 时间复杂度：O(nlogn)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findContentChildren(vector<int>& g, vector<int>& s) 
    {
        int m = g.size(), n = s.size();

        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int ret = 0, gi = 0, si = 0;
        while (gi < m && si < n)
        {
            if (s[si] >= g[gi])
            {
                ret++;
                gi++;
            }
            si++;
        }

        return ret;
    }
};

int main()
{
    vector<int> v11 = {1,2,3}, v12 = {1,1};
    vector<int> v21 = {1,2}, v22 = {1,2,3};
    Solution sol;

    cout << sol.findContentChildren(v11, v12) << endl;
    cout << sol.findContentChildren(v21, v22) << endl;

    return 0;
}
